class Solution
{
public:
    string baseNeg2(int n)
    {
        if (n == 0)
        {
            return "0";
        }
        string result;
        while (n != 0)
        {
            if (n % (-2) == 0)
            {
                result.push_back('0');
                n /= -2;
            }
            else if (n % (-2) == 1)
            {
                result.push_back('1');
                n /= -2;
            }
            else
            {
                result.push_back('1');
                n = n / (-2) + 1;
            }
        }
        return {result.rbegin(), result.rend()};
    }
};